#include <stdio.h>
#include <stdlib.h>
#include "BinTree.h"

void PreOrderTraversal(BinTree BT)
{
    if(BT)
    {
        printf("%d\n",BT->Data);
        PreOrderTraversal(BT->Left);
        PreOrderTraversal(BT->Right);
    }
}

void InOrderTraversal(BinTree BT)
{
    if(BT)
    {
        InOrderTraversal(BT->Left);
        printf("%d\n",BT->Data);
        InOrderTraversal(BT->Right);
    }
}

void PostOrderTraversal(BinTree BT)
{
    if(BT)
    {
        PostOrderTraversal(BT->Left);
        PostOrderTraversal(BT->Right);
        printf("%d\n",BT->Data);
    }
}

int GetHeight(BinTree BT)
{
    int LeftHeight,RightHeight,MaxHeight;
    if(BT)
    {
        LeftHeight = GetHeight(BT->Left);
        RightHeight = GetHeight(BT->Right);
        MaxHeight = LeftHeight > RightHeight ? LeftHeight:RightHeight;
        return MaxHeight + 1;
    }
    else
    {
        return 0;
    }

}

Position BSTFind(int x,BinTree BST)
{
    /*尾递归实现
    if(!BST)
        return NULL;
    if(BST->Data > x)
        return BSTFind(x,BST->Left);
    else if(BST->Data < x)
        return BSTFind(x,BST->Right);
    else
        return BST;*/
    //循环实现
    while(BST)
    {
        if(BST->Data > x)
        {
            BST = BST->Left;
        }
        else if(BST->Data < x)
        {
            BST = BST->Right;
        }
        else
            return BST;
    }
    return NULL;
}

Position FindMin(BinTree BST)
{
    /*尾递归实现
    if(!BST)
        return NULL;
    else if(BST->Left != NULL)
    {
        return FindMin(BST->Left);
    }
    else
    {
        return BST;
    }*/
    //循环实现
    if(BST != NULL)
    {
        while(BST->Left != NULL)
        {
            BST = BST->Left;
        }
    }
    return BST;
}

Position FindMax(BinTree BST)
{
    /*尾递归实现
    if(!BST)
        return NULL;
    else if(BST->Right)
        return FindMax(BST->Right)
    else
        return BST;
        */
    //循环实现
    if(BST)
    {
        while(BST->Right)
            BST = BST->Right;
    }
    return BST;
}

BinTree BSTInsert(int x,BinTree BST)
{
    if(!BST)
    {
        BST = (BinTree)malloc(sizeof(struct TreeNode));
        BST->Data = x;
        BST->Left = NULL;
        BST->Right = NULL;
    }
    else
    {
        if(x < BST->Data)
            BST->Left = BSTInsert(x,BST->Left);
        else if(x > BST->Data)
            BST->Right = BSTInsert(x,BST->Right);
    }
    return BST;
}

BinTree BSTDelete(int x,BinTree BST)
{
    Position Temp;
    if(!BST)
        printf("未找到要删除的数据!/n");
    else if(x < BST->Data)
        BST->Left = BSTDelete(x,BST->Left);
    else if(x > BST->Data)
        BST->Right = BSTDelete(x,BST->Right);
    else
    {
        if(BST->Left && BST->Right)
        {
            Temp = FindMin(BST->Right);

            BST->Data = Temp->Data;
            BST->Right = BSTDelete(BST->Data,BST->Right);
        }
        else
        {
            Temp = BST;
            if(!BST->Left)
                BST = BST->Right;
            else if(!BST->Right)
                BST = BST->Left;

            free(Temp);
        }
    }
    return BST;
}
